using System;
using System.Collections.Generic;

namespace Arcane.Source.Utils
{
    public class MinHeap<T> where T: IComparable<T>
    {
        private readonly List<T> items = [];
        public int Count => items.Count;

        public bool Conatins(T item) => items.Contains(item);

        public void Push(T num)
        {
            int idx = items.Count;
            items.Add(num);
            do
            {
                idx = Parent(idx);
                Heapify(idx);
            }
            while (idx >= 0);
        }

        public T Pop()
        {
            if (Count == 1)
            {
                var a = items[0];
                items.RemoveAt(0);
                return a;
            }
            
            var ans = items[0];
            items[0] = items[^1];
            items.RemoveAt(items.Count - 1);
            Heapify(0);
            
            return ans;
        }

        private void Heapify(int idx)
        {
            if (idx < 0) return;

            while (2 * idx < items.Count)
            {
                var lIdx = Left(idx);
                var rIdx = Right(idx);

                var mIdx = idx;

                if (lIdx < items.Count && items[mIdx].CompareTo(items[lIdx]) > 0)
                {
                    mIdx = lIdx;
                }

                if (rIdx < items.Count && items[mIdx].CompareTo(items[rIdx]) > 0)
                {
                    mIdx = rIdx;
                }

                if (mIdx == idx) break;

                Swap(idx, mIdx);
                idx = mIdx;
            }
        }
        private void Swap(int i, int j) => (items[i], items[j]) = (items[j], items[i]);

        public static int Parent(int index) => (index + 1) / 2 - 1;
        public static int Left(int index) => index * 2 + 1;
        public static int Right(int index) => index * 2 + 2;
    }
}